Over the past decades, iteratively decodable codes, such as Turbo-codes and LDPC (Low Density, Parity Check) codes, have improved the area of error control coding, and these codes have found their way towards applications and standards. Although these codes have shown impressive results for binary transmissions where long code-words (for instance N higher than 10000) are used over ergodic memoryless channels, their advantage compared to other coding schemes weakens when the application constraints include: (i) Very high-throughput transmission requiring multi-antenna communication or very-high order modulation (256-QAM and beyond), (ii) short frame transmission (typically N=[500, 3000]), when latency issue is concerned to ensure real-time transmissions, or (iii) quasi-error free transmission, where very low frame error rates (FER) are required (typically below FER=10−9).
After the early works of Davey, non-binary (NB) generalizations of LDPC codes have been extensively studied in the academic world. This includes in particular non-binary LDPC codes defined on larger order Galois fields GF(q). The important gains that NB-LDPC codes provide have to be balanced with the increased decoding complexity of NB-LDPC decoders, which has often been thought as an unavoidable bottleneck preventing the implementation of NB-LDPC decoders in practical apparatus.
It has been shown that simplified, sub-optimal implementations of NB-LDPC decoders are industrially feasible, in terms of implementation complexity, the complexity of the check-node operator has been reduced from O(q2), for a direct implementation of the belief propagation (BP) update equations [4], to O(nm log nm), with nm<<q, using an Extended Min-Sum (EMS) algorithm. The EMS algorithm is known based on the algorithm of Declercq et al described in “Decoding Algorithms for NB-LDPC Codes over GF(q)”, IEEE Trans. On Commun., vol. 55(4), pp. 633-643, April 2007. A representation of the check-node update and use such representation to limit the number of configurations in the EMS algorithm from K. Gunnam et al, in “Value-reuse properties of min-sum for GF(q)”, Texas A&M University Technical Note, October 2006. Both of these references are incorporated by reference herein.
The EMS algorithm has received much attention as it reduces both the computational and the storage complexities by choosing only nm most reliable values from each incoming vector message. With only nm values in each message, the EMS algorithm builds configuration sets conf(nm,nc), where nc is the number of deviations from the most reliable output configuration, and computes the extrinsic messages using those sets.
However, a need is still present to lower the ordering complexity of the check-node processing, the memory requirements and the decoding latency since these constraints are not specifically reduced by the here-above EMS algorithm, in particular in view of the applications: windshield wiper devices, connecting rod for transmission, error correction coding for food packaging, error-correcting code magnetic recording applications, etc.
In particular, iterative forward-backward (F/B) approaches are used in computing check-node output messages. The storage of the intermediate results of the forward and backward computations requires a large memory as well as involving more computations.